package com.arron.algorithm.leetcodetop100.数组;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class 合并区间 {


    // [[1,4],[0,4]],[1,4],[0,0]
    public int[][] merge(int[][] intervals) {

        if (intervals.length == 1) {
            return intervals;
        }
        int preEnd = -1;
        int preStart = Integer.MAX_VALUE;


        //对intervals 以左端点进行升序排序
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);

        List<List<Integer>> res = new ArrayList<>();
        for (int[] interval : intervals) {
            if (preEnd >= interval[0]) {
                if (res.size() != 0) {
                    res.remove(res.size() - 1);
                }
                res.add(Arrays.asList(Math.min(preStart, interval[0]), Math.max(preEnd, interval[1])));
            } else {
                res.add(Arrays.asList(interval[0], interval[1]));
            }
            preStart = res.get(res.size() - 1).get(0);
            preEnd = res.get(res.size() - 1).get(1);
        }

        int[][] arrays = new int[res.size()][2];
        for (int i = 0; i < res.size(); i++) {
            for (int j = 0; j < 2; j++) {
                arrays[i][j] = res.get(i).get(j);
            }
        }
        return arrays;
    }


    public int[][] merge_plus(int[][] intervals) {
        if (intervals.length ==1){
            return intervals;
        }



        //对intervals 以左端点进行排序
        Arrays.sort(intervals,(a,b)->a[0]-b[0]);

        int start = intervals[0][0] ;
        int end = intervals[0][1] ;
        int newLength = 0;
        for (int i = 1; i < intervals.length; i++) {
            if(intervals[i][1] < end){
                continue;
            }else if(intervals[i][0] <= end){
                end = intervals[i][1];
            }else{
                intervals[newLength][0] = start;
                intervals[newLength][1] = end;
                start = intervals[i][0];
                end = intervals[i][1];
                newLength++;
            }
        }
        intervals[newLength][0] = start;
        intervals[newLength][1] = end;

        int[][] newIntervals = new int[newLength+1][2];
        for (int i = 0; i < newIntervals.length; i++) {
            newIntervals[i][0] = intervals[i][0];
            newIntervals[i][1] = intervals[i][1];
        }
        return newIntervals;
    }


}
